﻿using System;
using System.Collections;
using System.Collections.Generic;

namespace psieve.sieve
{
    public class Sundaram : ISieve
    {
        public IEnumerable<long> Sieve(int end)
        {
            end = end/2;

            BitArray ray = new BitArray(end + 1, true);

            int endI = (int) Math.Ceiling(Math.Sqrt(end / 2.0));

            for (int i = 1; i <= endI; i++)
            {
                long i2 = 2*i;

                for (long idx = i2 + 2 * i * i; idx <= end; idx += 1 + i2)
                    ray[(int) idx] = false;
            }

            yield return 2;

            for (int p = 1; p <= end; p++)
                if (ray[p])
                    yield return 2 * p + 1;
        }
    }
}
